1900E - Transitive Graph - CodeForces Solution

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define int long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 100000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
template<class T> using ordered_set =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod =  1000000007 ;
const int mod1 = 998244353 ;
const int N = 4e5 + 10 ;
mt19937 R(time(0));
map < int , int > ma , ma1 ;

vector< int > adj[ N ], adj_rev[ N ];
vector<bool> used;
vector<int> order, component;

void dfs1(int v) {
    used[v] = true;

    for (auto u : adj[v])
        if (!used[u])
            dfs1(u);

    order.push_back(v);
}
map < pair < int , int > , int > bn ; 
void dfs2(int v) {
    used[v] = true;
    component.push_back(v);

    for (auto u : adj_rev[v])
        if (!used[u])
            dfs2(u);
}

void solve() {
    int n, m ;
     cin >> n >> m ;
     int a[ n + 5 ] ; 
	 FOR( i , n ) cin >> a[ i + 1 ] ;
	 bn.clear() ;
     used.clear() ; order.clear() ; component.clear() ;
     FOR( i , n + 10 ){
     	adj[ i ].clear() ;
     	adj_rev[ i ].clear() ;
 	 }
     FOR( i , m ){
        int a, b ;
        cin >> a >> b ; 
        if( a == b ) continue ; 
        if( bn.find( { a , b } ) != bn.end() ) continue ; 
        bn[ { a , b } ] = 1 ;
        adj[a].push_back(b);
        adj_rev[b].push_back(a);
    }

    used.assign(n+5, false);

    for (int i = 1; i <= n ; i++)
        if (!used[i])
            dfs1(i);

    used.assign(n+5, false);
    reverse(order.begin(), order.end());
	    	    
	vector<int> roots(n+5, 0);
	vector<int> root_nodes;
	vector<vector<int>> adj_scc(n+5) , xix(n + 5);
    int sm[ n + 10 ] , ss[ n + 10 ];
    FOR( i , n + 10 ) sm[ i ] = ss[ i ]= 0 ; 
    
	for (auto v : order)
	    if (!used[v]) {
	        dfs2(v);
	
	        int root = component.front();
	        for (auto u : component) roots[u] = root, sm[ root ] += a[ u ] ;
	        ss[ root ] = component.size() ;
	        root_nodes.push_back(root);
	
	        component.clear();
	    }
	
	
	for (int v = 1; v <= n; v++)
	    for (auto u : adj[v]) {
	        int root_v = roots[v],
	            root_u = roots[u];
	
	        if (root_u != root_v)
	            adj_scc[root_v].push_back(root_u);
	            xix[ root_u ].pb( root_v ) ; 
	    }        
     // now that we have a graph
     // lets find the value 
     pair < int , int > val[ n + 10 ] ;
	 int nn[ n + 5 ] ;
	 set < pair < int , int > > sus ; 
	 
	 for( auto x : root_nodes ){
        sus.insert( { adj_scc[ x ].size() , x } ) ;
        nn[ x ] = adj_scc[ x ].size() ;
	 }
	 pair < int , int > ans ;
	 ans.first = 0 ;
	 while( true ){
	 	if( sus.size() == 0 ) break ;
	 	pair < int , int > x = *sus.begin() ;
	 	sus.erase( sus.begin() ) ; 
	 //	debug ;
	 	for( auto y : xix[ x.s ] ){
	 		if( sus.find( { nn[ y ], y } ) == sus.end() ) continue ;
	 	  sus.erase( sus.find( { nn[ y ] , y } ) ) ;
		   nn[ y ] -- ; 
		   sus.insert( { nn[ y ] , y  } ) ; 	
		}
		pair < int , int > p ;
		p.f = 0 ;
		for( auto y : adj_scc[ x.s ] ){
		   if( val[ y ].f > p.f ){
		   	 p = val[ y ] ;
		   	 continue ; 
		   }	
		   if( val[ y ].f < p.first ) continue ;
		   p.s = min( val[ y ].s , p.s ) ; 
		}
		p.f += ss[ x.s ] ;
		p.s += sm[ x.s ] ;
		val[ x.s ] = p ; 
		if( val[ x.s ].f > ans.f ){
			ans = val[ x.s ] ; 
			continue ; 
		} 
		if( val[ x.s ].f < ans.f ) continue ;
		ans.s = min( ans.s , val[ x.s ].s ) ;
	 }
	 cout << ans.f << " " << ans.s << "\n" ;
}
signed main() {
   ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
   int t = 1 ; cin >> t ;
   while( t -- ){
   	 solve() ;
   }

}